package leetcode;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @author yinlei
 * @date 2018/6/26
 * @since 1.0.0
 */
public class N094BinaryTreeInorderTraversal {

    public static void main(String[] args) {
        TreeNode root = array2Tree(new Integer[] {1, null, 2, 3});
        List<Integer> list = inorderTraversal(root);
        System.out.println(list);
    }

    private static TreeNode array2Tree(Integer[] integers) {
        TreeNode root = new TreeNode(integers[0]);

        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        return root;
    }

    static public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    // 使用循环
    static public List<Integer> inorderTraversal(TreeNode root) {

        LinkedList<Integer> list = new LinkedList<>();

        Stack<TreeNode> treeNodeStack = new Stack<>();
        TreeNode node = root;
        boolean pop = false;

        while (node != null) {

            if (!pop && node.left != null) {
                treeNodeStack.push(node);
                node = node.left;
                continue;
            }
            pop = false;

            list.add(node.val);
            if (node.right != null) {
                node = node.right;
            } else {
                if (treeNodeStack.isEmpty()) {
                    break;
                }
                node = treeNodeStack.pop();
                pop = true;
            }
        }

        return list;
    }
}
